package com.qisi.kandroidshalon.leetcode.linklist;

import android.util.Log;

import com.qisi.kandroidshalon.leetcode.Util;

public class KList {

    /**
     * 对一个链表做逆序
     *
     * @param head
     */
    public static ListNode reverseList(ListNode head) {
        ListNode pre = null;//已经逆序好的头节点
        ListNode cur = head;//待调整的头节点
        ListNode next;//待调整节点的下一个节点，用于迭代cur
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            //cur往前走
            cur = next;
        }
        return pre;
    }

    /**
     * 给定一个链表的 头节点 head ，请判断其是否为回文链表。
     * <p>
     * 如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。
     * 思路：快慢指针，注意区分奇偶数节点
     */
    public static boolean isPalindrome(ListNode head) {
        if (head == null) {
            return false;
        }
        //前半区尾部
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //局部范围逆序
        slow.next = revertList(slow.next);
        //不管奇偶，都从后半部分开始逐个比较，知道尾部
        ListNode left = head;
        ListNode right = slow.next;


        //后半段直到尾部节点
        while (right != null) {
            if (right.value != left.value) {
                return false;
            }
            left = left.next;
            right = right.next;
        }
        //还原
        slow.next = revertList(slow.next);
        return true;
    }

    /**
     * 局部范围内的逆序,返回逆序后的节点,此方法会断开start节点和原来的联系！
     *
     * @param start
     * @return
     */
    private static ListNode revertList(ListNode start) {
        ListNode pre = null;//已经逆序好的头节点
        ListNode cur = start;//待调整的头节点
        ListNode next;//待调整节点的下一个节点，用于迭代cur
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            //cur往前走
            cur = next;
        }
        return pre;
    }


    /**
     * k个一组，做逆序,
     * 思路： 部分逆序，需要区间的前节点与后节点,这样区间内部做逆序后，能重新连接，所以需要引入head的前节点
     *
     * @param head
     * @param k
     * @return
     */
    public static ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        ListNode preHead = new ListNode(-1);
        preHead.next = head;

        //每一组的前驱节点
        ListNode preStart = preHead;
        while (true) {
            //区间的起止节点
            ListNode start = preStart.next;
            ListNode end = start;
            //找到区间的end结束节点
            for (int i = 0; i < k - 1 && end != null; i++) {
                end = end.next;
            }

            if (end == null) {
                break;
            }

            //先断开区间和后面的连接，记录下一分组的开始节点
            ListNode nextStart = end.next;
            end.next = null;
            ListNode revertHead = revertList(preStart.next);
            //连接前缀节点
            preStart.next = revertHead;
            //连接后续节点, start变成end
            start.next = nextStart;
            //更新下一组的起点
            preStart = start;
        }
        return preHead.next;
    }

    /**
     * 141. 环形链表
     * 给你一个链表的头节点 head ，判断链表中是否有环。
     * <p>
     * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
     * <p>
     * 如果链表中存在环 ，则返回 true 。 否则，返回 false 。
     */

    public static boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        //此方法只用于判断是否有环，因为奔跑起点不一样，所以是找不到正确的相遇点的
        ListNode slow = head;
        ListNode fast = head;

        while (slow != null && fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {//相遇了
                break;
            }
        }
        // 如果没有环fast会走到尾部节点
        if (fast != null && fast.next != null) {//有环
            slow = head;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            Log.i(Util.TAG, "环入口节点:" + slow.value);
            return true;
        }
        return false;
    }

}
